package com.leetcode.no1140;

import java.util.*;

public class Solution {
    List<Integer> vals = new ArrayList<>();

    public int stoneGameII(int[] piles) {
        int res = 0;
        int M = 1;

        LinkedList<Integer> track = new LinkedList<>();

        backtrack(piles, 0, M, track);

        return res;
    }

    public void backtrack(int[] piles, int index, int M, LinkedList<Integer> track) {
        if (piles.length < 1)
            return;

        if (2 * M >= piles.length - index) {
            // 直接全部拿完
            return;
        }

        // 在[1, 2*M]中做选择
        for (int i = 1; i < 2 * M; i++) {
            track.add(i);
        }

        track.removeLast();
    }
}


class Solution01 {

    public int stoneGameII(int[] piles) {
        int len = piles.length;
        int[][] memo = new int[len][len + 1];

        // 前缀和
        int[] preSum = new int[len + 1];

        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + piles[i];
        }
        //        x + y = preSum[len];
        //        x - y = res;
        int res = dfs(piles, 0, 1, preSum, memo);

        // 由于得到的是相对分数，需要转换成为绝对分数
        return (preSum[len] + res) / 2;


    }

    private int dfs(int[] piles, int begin, int M, int[] preSum, int[][] memo) {
        return 0;
    }

}


class Solution02 {

    public int stoneGameII(int[] piles) {
        int len = piles.length;
        if(len < 1){
            return 0;
        }
        if(len == 1){
            return piles[0];
        }

        int sum = 0;

        // dp[i][j]表示M = i的情况下,剩余piles[j : len - 1]堆时，先取的人能获得的最多石子数
        // 行为i 列为j  因为行多了一行j为0的情况  这里先不考虑优化数组空间，重在思路

        int[][] dp = new int[len+1][len];

        // 基本情况 最后一列 此时i=len-1,即只剩下一堆
        for (int row = 1; row < len + 1; row++) {
            dp[row][len - 1] = piles[len - 1];
        }


        // 从后往前推，推到第一列
        for (int j = len - 1; j >= 0; j--) {
            sum += piles[j];

            for (int M = 1; M <= len; M++) {
                // 可以一次性全部拿完  剩余堆数小于2*M时
                if (len - j <= 2 * M) {
                    dp[M][j] = sum;
                } else {
                    for (int x = 1; x <= 2 * M; x++) {
                        dp[M][j] = Math.max(
                                dp[M][j],
                                sum - dp[Math.max(M, x)][j + x]
                        );
                    }
                }
            }
        }

        // 答案为dp[0][1]
        // 剩余piles[0 : len - 1]堆时，M = 1的情况下，先取的人能获得的最多石子数
        return dp[1][0];
    }

}

//
//class Solution:
//        def stoneGameII(self, piles: List[int]) -> int:
//        # 数据规模与记忆化
//        n, memo = len(piles), dict()
//
//        # s[i] 表示第 i 堆石子到最后一堆石子的总石子数
//        s = [0] * (n + 1)
//        for i in range(n - 1, -1, -1):
//        s[i] = s[i + 1] + piles[i]
//
//        # dfs(i, M) 表示从第 i 堆石子开始取，最多能取 M 堆石子所能得到的最优值
//        def dfs(i, M):
//        # 如果已经搜索过，直接返回
//        if (i, M) in memo:
//        return memo[(i, M)]
//        # 溢出拿不到任何石子
//        if i >= n:
//        return 0
//        # 如果剩余堆数小于等于 2M， 那么可以全拿走
//        if i + M * 2 >= n:
//        return s[i]
//        # 枚举拿 x 堆的最优值
//        best = 0
//        for x in range(1, M * 2 + 1):
//        # 剩余石子减去对方最优策略
//        best = max(best, s[i] - dfs(i + x, max(x, M)))
//        # 记忆化
//        memo[(i, M)] = best
//        return best
//
//        return dfs(0, 1)
//
